home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / russell / gc32.lha / stubborn.c < prev    next >
C/C++ Source or Header  |  1993-07-14  |  9KB  |  308 lines
  1.  
  2. /* 
  3.  * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
  4.  * Copyright (c) 1991-1993 by Xerox Corporation.  All rights reserved.
  5.  *
  6.  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
  7.  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
  8.  *
  9.  * Permission is hereby granted to copy this garbage collector for any purpose,
  10.  * provided the above notices are retained on all copies.
  11.  */
  12.  
  13.  
  14. #include "gc_private.h"
  15.  
  16. # ifdef STUBBORN_ALLOC
  17. /* Stubborn object (hard to change, nearly immutable) allocation. */
  18.  
  19.  
  20. # ifdef ALL_INTERIOR_POINTERS
  21. #   define SMALL_OBJ(bytes) ((bytes) < WORDS_TO_BYTES(MAXOBJSZ))
  22. # else
  23. #   define SMALL_OBJ(bytes) ((bytes) <= WORDS_TO_BYTES(MAXOBJSZ))
  24. # endif
  25.  
  26. /* Data structure representing immutable objects that     */
  27. /* are still being initialized.                */
  28. /* This is a bit baroque in order to avoid acquiring    */
  29. /* the lock twice for a typical allocation.        */
  30.  
  31. extern_ptr_t * GC_changing_list_start;
  32.  
  33. # ifdef THREADS
  34.     VOLATILE
  35. # endif
  36. extern_ptr_t * GC_changing_list_current;
  37.     /* Points at last added element.  Also (ab)used for        */
  38.     /* synchronization.  Updates and reads are assumed atomic.    */
  39.  
  40. extern_ptr_t * GC_changing_list_limit;
  41.     /* Points at the last word of the buffer, which is always 0    */
  42.     /* All entries in (GC_changing_list_current,            */
  43.     /* GC_changing_list_limit] are 0                */
  44.  
  45.  
  46. void GC_stubborn_init()
  47. {
  48. #   define INIT_SIZE 10
  49.  
  50.     GC_changing_list_start = (extern_ptr_t *)
  51.                 GC_generic_malloc_inner(
  52.                     (word)(INIT_SIZE * sizeof(extern_ptr_t)),
  53.                     PTRFREE);
  54.     bzero((char *)GC_changing_list_start,
  55.           (int)(INIT_SIZE * sizeof(extern_ptr_t)));
  56.     if (GC_changing_list_start == 0) {
  57.         GC_err_printf0("Insufficient space to start up\n");
  58.         ABORT("GC_stubborn_init: put of space");
  59.     }
  60.     GC_changing_list_current = GC_changing_list_start;
  61.     GC_changing_list_limit = GC_changing_list_start + INIT_SIZE - 1;
  62.     * GC_changing_list_limit = 0;
  63. }
  64.  
  65. /* Compact and possibly grow GC_uninit_list.  The old copy is        */
  66. /* left alone.    Lock must be held.                    */
  67. /* When called GC_changing_list_current == GC_changing_list_limit    */
  68. /* which is one past the current element.                */
  69. /* When we finish GC_changing_list_current again points one past last    */
  70. /* element.                                */
  71. /* Invariant while this is running: GC_changing_list_current        */
  72. /* points at a word containing 0.                    */
  73. /* Returns FALSE on failure.                        */
  74. bool GC_compact_changing_list()
  75. {
  76.     register extern_ptr_t *p, *q;
  77.     register int count = 0;
  78.     word old_size = GC_changing_list_limit-GC_changing_list_start+1;
  79.     register word new_size = old_size;
  80.     extern_ptr_t * new_list;
  81.     
  82.     for (p = GC_changing_list_start; p < GC_changing_list_limit; p++) {
  83.         if (*p != 0) count++;
  84.     }
  85.     if (2 * count > old_size) new_size = 2 * count;
  86.     new_list = (extern_ptr_t *)
  87.             GC_generic_malloc_inner(
  88.                     new_size * sizeof(extern_ptr_t), PTRFREE);
  89.             /* PTRFREE is a lie.  But we don't want the collector to  */
  90.             /* consider these.  We do want the list itself to be        */
  91.             /* collectable.                          */
  92.     if (new_list == 0) return(FALSE);
  93.     bzero((char *)new_list, (int)(new_size * sizeof(extern_ptr_t)));
  94.     q = new_list;
  95.     for (p = GC_changing_list_start; p < GC_changing_list_limit; p++) {
  96.         if (*p != 0) *q++ = *p;
  97.     }
  98.     GC_changing_list_start = new_list;
  99.     GC_changing_list_limit = new_list + new_size - 1;
  100.     GC_changing_list_current = q;
  101.     return(TRUE);
  102. }
  103.  
  104. /* Add p to changing list.  Clear p on failure.    */
  105. # define ADD_CHANGING(p) \
  106.     {    \
  107.         register struct hblk * h = HBLKPTR(p);    \
  108.         register word index = PHT_HASH(h);    \
  109.         \
  110.         set_pht_entry_from_index(GC_changed_pages, index);    \
  111.     }    \
  112.     if (*GC_changing_list_current != 0 \
  113.         && ++GC_changing_list_current == GC_changing_list_limit) { \
  114.         if (!GC_compact_changing_list()) (p) = 0; \
  115.     } \
  116.     *GC_changing_list_current = p;
  117.  
  118. void GC_change_stubborn(p)
  119. extern_ptr_t p;
  120. {
  121.     DISABLE_SIGNALS();
  122.     LOCK();
  123.     ADD_CHANGING(p);
  124.     UNLOCK();
  125.     ENABLE_SIGNALS();
  126. }
  127.  
  128. void GC_end_stubborn_change(p)
  129. extern_ptr_t p;
  130. {
  131.     register extern_ptr_t * my_current = GC_changing_list_current;
  132.     register bool tried_quick;
  133.     
  134.     if (*my_current == p) {
  135.         /* Hopefully the normal case.                    */
  136.         /* Compaction could not have been running when we started.    */
  137.         *my_current = 0;
  138. #    ifdef THREADS
  139.           if (my_current == GC_changing_list_current) {
  140.             /* Compaction can't have run in the interim.     */
  141.             /* We got away with the quick and dirty approach.   */
  142.             return;
  143.           }
  144.           tried_quick = TRUE;
  145. #    else
  146.       return;
  147. #    endif
  148.     } else {
  149.         tried_quick = FALSE;
  150.     }
  151.     DISABLE_SIGNALS();
  152.     LOCK();
  153.     my_current = GC_changing_list_current;
  154.     for (; my_current >= GC_changing_list_start; my_current--) {
  155.         if (*my_current == p) {
  156.             *my_current = 0;
  157.             UNLOCK();
  158.             ENABLE_SIGNALS();
  159.             return;
  160.         }
  161.     }
  162.     if (!tried_quick) {
  163.         GC_err_printf1("Bad arg to GC_end_stubborn_change: 0x%lx\n",
  164.                    (unsigned long)p);
  165.         ABORT("Bad arg to GC_end_stubborn_change");
  166.     }
  167.     UNLOCK();
  168.     ENABLE_SIGNALS();
  169. }
  170.  
  171. /* Allocate lb bytes of composite (pointerful) data    */
  172. /* No pointer fields may be changed after a call to    */
  173. /* GC_end_stubborn_change(p) where p is the value    */
  174. /* returned by GC_malloc_stubborn.            */
  175. # ifdef __STDC__
  176.     extern_ptr_t GC_malloc_stubborn(size_t lb)
  177. # else
  178.     extern_ptr_t GC_malloc_stubborn(lb)
  179.     size_t lb;
  180. # endif
  181. {
  182. register ptr_t op;
  183. register ptr_t *opp;
  184. register word lw;
  185. extern_ptr_t result;
  186. DCL_LOCK_STATE;
  187.  
  188.     if( SMALL_OBJ(lb) ) {
  189. #       ifdef MERGE_SIZES
  190.       lw = GC_size_map[lb];
  191. #    else
  192.       lw = ROUNDED_UP_WORDS(lb);
  193. #       endif
  194.     opp = &(GC_sobjfreelist[lw]);
  195.     FASTLOCK();
  196.         if( !FASTLOCK_SUCCEEDED() || (op = *opp) == 0 ) {
  197.             FASTUNLOCK();
  198.             result = GC_generic_malloc((word)lb, STUBBORN);
  199.             goto record;
  200.         }
  201.         *opp = obj_link(op);
  202.         obj_link(op) = 0;
  203.         GC_words_allocd += lw;
  204.         FASTUNLOCK();
  205.         result = (extern_ptr_t) op;
  206.         ADD_CHANGING(result);
  207.         FASTUNLOCK();
  208.         return(result);
  209.    } else {
  210.        result = (extern_ptr_t)
  211.               GC_generic_malloc((word)lb, STUBBORN);
  212.    }
  213. record:
  214.    DISABLE_SIGNALS();
  215.    LOCK();
  216.    ADD_CHANGING(result);
  217.    UNLOCK();
  218.    ENABLE_SIGNALS();
  219.    return(result);
  220. }
  221.  
  222.  
  223. /* Functions analogous to GC_read_dirty and GC_page_was_dirty.    */
  224. /* Report pages on which stubborn objects were changed.        */
  225. void GC_read_changed()
  226. {
  227.     register extern_ptr_t * p = GC_changing_list_start;
  228.     register extern_ptr_t q;
  229.     register struct hblk * h;
  230.     register word index;
  231.     
  232.     if (p == 0) /* initializing */ return;
  233.     bcopy((char *)GC_changed_pages, (char *)GC_prev_changed_pages,
  234.           (int)(sizeof GC_changed_pages));
  235.     bzero((char *)GC_changed_pages, (int)(sizeof GC_changed_pages));
  236.     for (; p <= GC_changing_list_current; p++) {
  237.         if ((q = *p) != 0) {
  238.             h = HBLKPTR(q);
  239.             index = PHT_HASH(h);
  240.             set_pht_entry_from_index(GC_changed_pages, index);
  241.         }
  242.     }
  243. }
  244.  
  245. bool GC_page_was_changed(h)
  246. struct hblk * h;
  247. {
  248.     register word index = PHT_HASH(h);
  249.     
  250.     return(get_pht_entry_from_index(GC_prev_changed_pages, index));
  251. }
  252.  
  253. /* Remove unreachable entries from changed list. Should only be    */
  254. /* called with mark bits consistent and lock held.        */
  255. void GC_clean_changing_list()
  256. {
  257.     register extern_ptr_t * p = GC_changing_list_start;
  258.     register extern_ptr_t q;
  259.     register ptr_t r;
  260.     register unsigned long count = 0;
  261.     register unsigned long dropped_count = 0;
  262.     
  263.     if (p == 0) /* initializing */ return;
  264.     for (; p <= GC_changing_list_current; p++) {
  265.         if ((q = *p) != 0) {
  266.             count++;
  267.             r = (ptr_t)GC_base(q);
  268.             if (r == 0 || !GC_is_marked(r)) {
  269.                 *p = 0;
  270.                 dropped_count++;
  271.         }
  272.         }
  273.     }
  274. #   ifdef PRINTSTATS
  275.       if (count > 0) {
  276.         GC_printf2("%lu entries in changing list: reclaimed %lu\n",
  277.                   (unsigned long)count, (unsigned long)dropped_count);
  278.       }
  279. #   endif
  280. }
  281.  
  282. #else /* !STUBBORN_ALLOC */
  283.  
  284. # ifdef __STDC__
  285.     extern_ptr_t GC_malloc_stubborn(size_t lb)
  286. # else
  287.     extern_ptr_t GC_malloc_stubborn(lb)
  288.     size_t lb;
  289. # endif
  290. {
  291.     return(GC_malloc(lb));
  292. }
  293.  
  294. /*ARGSUSED*/
  295. void GC_end_stubborn_change(p)
  296. extern_ptr_t p;
  297. {
  298. }
  299.  
  300. /*ARGSUSED*/
  301. void GC_change_stubborn(p)
  302. extern_ptr_t p;
  303. {
  304. }
  305.  
  306.  
  307. #endif
  308.